#define _CRT_SECURE_NO_WARNINGS 1

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define NULL 0
typedef int KeyType;
typedef struct {
	KeyType key;
}ElemType;

int Haxi(KeyType key, int m)            //根据哈希表长m，构造除留余数法的哈希函数Haxi*
{
	int i, p, flag;
	for (p = m; p >= 2; p--)                   		/*p为不超过m的最大素数*/
	{
		for (i = 2, flag = 1; i <= p / 2 && flag; i++)
		{
			if (p % i == 0)
			{
				flag = 0;
			}
			if (flag == 1)
			{
				break;
			}
		}
		return key % p;                    //哈希函数
	}
}
/*从键盘输入n个数据，存入数据表ST(采用动态分配的数组空间)*/
void Inputdata(ElemType** ST, int n)
{
	int i;
	(*ST) = (ElemType*)malloc(n * sizeof(ElemType));
	printf("\n 请输入 %d 个数据: ", n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &((*ST)[i].key));
	}
}

	/*根据数据表ST，构造哈希表HAXI*，n、m分别为数据集合ST和哈希表的长度*/
void Createhaxi(ElemType * *HAXI, ElemType * ST, int n, int m)
{
	int i, j = 0;
	(*HAXI) = (ElemType*)malloc(m * sizeof(ElemType));
	for (i = 0; i < m; i++)
	{
		(*HAXI)[i].key = NULL;                        /*初始化哈希为空表（以0表示空)*/
	}
	for (i = 0; i < n; i++)
	{
		j = Haxi(ST[i].key, m);                         /*获得直间哈希地址ַ*/
		while ((*HAXI)[j].key != NULL)                /*用线性探测器再散列技术确定存放位置*/
		{
			j = (j + 1) % m;
		}
		(*HAXI)[j].key = ST[i].key;                  /*将元素存入哈希表的相应位置*/
	}
}

/*在表长为m的哈希表中查找关键字等于key的元素，并用time记录比较次数，若查找
成功，函数返回值为其在哈希表中的位置，否则返回-1*/
int Search(ElemType * HAXI, KeyType key, int m, int* time)
{
	int i;
	*time = 1;
	i = Haxi(key, m);
	while (HAXI[i].key != 0 && HAXI[i].key != key)
	{
		i++;
		++* time;
	}
	if (HAXI[i].key == 0)
	{
		return -1;
	}
	else
	{
		return i;
	}
}

void main()
{
	ElemType* ST, * HAXI;
	KeyType key;
	int i, n, m, stime, time;
	char ch;
	printf("\n 请输入 n&&m(n<=m): ");						/*输入关键字集合元素个数和HAXI表长*/
	scanf("%d%d", &n, &m);
	Inputdata(&ST, n);										/*调用函数，输入n个数据*/
	Createhaxi(&HAXI, ST, n, m);								/*建立哈希表*/
	/*输出已建立的哈希表*/
	printf("\n 哈希表为\n");
	for (i = 0; i < m; i++)
	{
		printf("%5d", i);
	}
	printf("\n");
	for (i = 0; i < m; i++)
	{
		printf("%5d", HAXI[i].key);
	}
	/*哈希表的查找，可进行多次查找*/
	do {
		printf("\n 请输入你想要查找的关键字:");
		scanf("%d", &key);
		i = Search(HAXI, key, m, &time);
		if (i != -1)
		{
			printf("\n 查找成功，位置是 %d", i);
			printf("\n 比较次数为 %d", time);
		}
		else
		{
			printf("\n 查找不成功！");
			printf("\n 比较次数为 %d", time);
		}
		printf("\n 继续吗(y/n):\n");
		ch = getch();
	} while (ch == 'y' || ch == 'Y');
	/*计算表在等概率情况下的平均查找长度，并输出*/
	for (stime = 0, i = 0; i < n; i++)
	{
		Search(HAXI, ST[i].key, m, &time);
		stime += time;
	}
	printf("\n 平均查找长度为 %5.2f\n", (float)stime / n);
	ch = getch();
}